#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

ListNode* createList(int arr[], int n) {
    if (n == 0) {
        return nullptr;
    }
    ListNode* head = new ListNode(arr[0]);
    ListNode* cur = head;

    for (int i = 1; i < n; i++) {
        cur->next = new ListNode(arr[i]);
        cur = cur->next;
    }

    return head;
}

void printList(ListNode* head) {
    if (head == nullptr) {
        cout << "null" << endl;
    }

    while (head) {
        cout << head->val;
        if (head->next) {
            cout << "->";
        }
        head = head->next;
    }

    cout << endl;
}

// null    1     2    null
//  pre   cur
//              pre   cur

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }

        return pre;
    }

    //         0   1   2   3    4
    // dummy   1   2   3   4    5
    //             2       4
    //         pre left   right afterRight
    // 只需要找到pre和right，left=pre->next, afterRight=right->next
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 头节点可能发生变化，所有使用哑节点
        ListNode* dummy = new ListNode(0, head);

        ListNode* pre = dummy;
        // 1. 找到pre节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }

        // 2. 找到right节点
        ListNode* rightNode = pre;
        for (int i = 0; i < right - left + 1; i++) {
            rightNode = rightNode->next;
        }

        // 3. 切断出一个子链表
        ListNode* leftNode = pre->next;
        ListNode* afterRight = rightNode->next;
        rightNode->next = nullptr;

        // 5. 反转子区间并拼接链表
        pre->next = reverseList(leftNode);
        leftNode->next = afterRight;

        return dummy->next;
    }
};

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    ListNode* list = createList(arr, sizeof(arr) / sizeof(int));

    printList(list);
    //printList(Solution().reverseList(list));
    printList(Solution().reverseBetween(list, 2, 4));
    return 0;
}